public class Tree {
    public class TreeNode{
        char val;
        TreeNode left;
        TreeNode right;
        public TreeNode(char val){
            this.val=val;
        }
    }
    public TreeNode createTree() {
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');

        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        E.right = H;
        return A;//就是根节点
    }
    public void order(TreeNode root){
        if(root==null){
            return;
        }
        //前序遍历
        System.out.println(root.val);
        order(root.left);
        order(root.right);
    }
    //获取节点个数
    public int numSize(TreeNode root){
        if(root==null){
            return 0;
        }
        return numSize(root.left)+numSize(root.right)+1;
    }
    //求叶子节点个数
    public int numLeave(TreeNode root){
        if(root==null){
            return 0;
        }
        if(root.left==null&&root.right==null){
            return 1;
        }
        return numLeave(root.left)+numLeave(root.right);
    }
    //第k层有多少节点
    public int getKnum(TreeNode root,int k){
        if(root==null){
            return 0;
        }
        if(k==1){
            return 1;
        }
        return getKnum(root.right,k-1)+getKnum(root.left,k-1);
    }
    //获取树的高度
    public int getHight(TreeNode root){
        if(root==null){
            return 0;
        }
        int leftnum=getHight(root.left);
        int rightnum=getHight(root.right);
        return Math.max(leftnum,rightnum)+1;
    }
    //找到val所在的节点
    public TreeNode searchVal(TreeNode root,char val){
        if(root==null){
            return null;
        }
        if(root.val==val){
            return root;
        }
        TreeNode ret=searchVal(root.left,val);
        if(ret!=null){
            return ret;
        }
        TreeNode ret2=searchVal(root.right,val);
        if(ret2!=null){
            return ret2;
        }
        return null;
    }
    //判断两颗树是否相同
    public boolean isSameTree(TreeNode p,TreeNode q){
        if(p==null&&q==null){
            return true;
        }
        if(q==null&&p!=null||q!=null&&p==null){
            return false;
        }
        if(q.val!=p.val){
            return false;
        }
        return isSameTree(q.left,p.left)&&isSameTree(q.right,p.right);
    }
    //另一颗树的子树   //这道题的思想是利用两个树是否相等,
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root==null){
            return false;
        }
        if(isSameTree(root,subRoot)){
            return true;
        }
        if(isSubtree(root.left,subRoot)){
            return true;
        }
        if(isSubtree(root.left,subRoot)){
            return true;
        }
        return false;
    }

    //反转二叉树
    public TreeNode invertTree(TreeNode root) {
        if(root==null){
            return null;
        }
        if(root.left == null && root.right == null) {
            return root;
        }
        TreeNode temp=null;
        temp=root.left;
        root.left=root.right;
        root.right=temp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }


    //判断一颗树是否是一颗平衡树
    public boolean isBalanced(TreeNode root) {
        if(root==null){
            return true;
        }
        int lefHeight=maxDep(root.left);
        int rightHight=maxDep(root.right);
        return Math.abs(lefHeight-rightHight)<=1
                &&isBalanced(root.left)&&isBalanced(root.right);
    }
    public int maxDep(TreeNode root){
        if(root==null){
            return 0;
        }
        int left=maxDep(root.left);
        int right=maxDep(root.right);
        return left>right?left+1:right+1;
    }
    public boolean isSymmetric(TreeNode root) {
        if(root==null){
            return true;
        }
        return isSymmetricChild(root.left,root.right);

    }
    public boolean isSymmetricChild(TreeNode rootleft,TreeNode rootright){
        if(rootleft==null&&rootleft==null){
            return true;
        }
        if(rootleft!=null&&rootright==null||rootleft==null&&rootright!=null){
            return false;
        }
        if(rootleft.val!= rootright.val){
            return false;
        }
        return isSymmetricChild(rootleft.left,rootright.right)
                &&isSymmetricChild(rootright.right,rootleft.right);
    }
    


}
